#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "general.h"
#include "sudoku.h"
#include "solver.h"

inline int bitCount (unsigned int u)
{
  unsigned int uCount;
  uCount = u 
             - ((u >> 1) & 033333333333) 
             - ((u >> 2) & 011111111111);
  return ((uCount + (uCount >> 3))
	  & 030707070707) % 63;
}

inline void clrNum (int num, cell * c)
{
  cell mask = 0x1;
  mask = mask << (num - 1);
  mask = ~mask;
  *c = *c & mask;
}

inline void setCell (int num, cell * c)
{
  cell mask = 0x1;
  mask = mask << (num - 1);
  *c = 0;
  *c = mask;
}

bool umkCell (Grid g, int x, int y)
{
  int xi, yi;
  int sx, sy;
  bool progress = FALSE;
  sx = getSubGridX(x);
  sy = getSubGridY(y);

  cell cur = gridIndex(g, x, y);
  cell mask = ~cur;
  for (yi = 0; yi < GRID_SIZE; yi++)
    {
      if (yi != y)
	{
	  if (gridIndex(g, x, yi) & cur)
	    {
	      progress = TRUE;
	      gridIndex(g, x, yi) = gridIndex(g, x, yi) & mask;
	    }
	}
    }
  for (xi = 0; xi < GRID_SIZE; xi++)
    {
      if (xi != x)
	{
	  if (gridIndex(g, xi, y) & cur)
	    {
	      progress = TRUE;
	      gridIndex(g, xi, y) = gridIndex(g, xi, y) & mask;
	    }
	}
    }
  for (yi = 0; yi < SUB_GRID_SIZE; yi++)
    {
      for (xi = 0; xi < SUB_GRID_SIZE; xi++)
	{
	  if (&gridIndex(g, x, y) != &subGridIndex(g, sx, sy, xi, yi))
	    {
	      if ((subGridIndex(g, sx, sy, xi, yi) & cur))
		{
		  progress = TRUE;
		  subGridIndex(g, sx, sy, xi, yi) = subGridIndex(g, sx, sy, xi, yi) & mask;
		}
	    }
	}
    }
  return progress;
}

void prtCell (cell c, int type)
{
  int i;
  cell mask = 0x1;
  char bin[GRID_SIZE + 1];
  bin[GRID_SIZE] = '\0';
  for (i = 0; i < GRID_SIZE; i++)
    {
      if (c & mask)
	{
	  bin[GRID_SIZE - 1 - i] = '1';
	}
      else
	{
	  bin[GRID_SIZE - 1 - i] = '0';
	}
      mask = mask << 1;
    }
  mask = 0x1;
  if (type == 1)
    {
      if (bitCount(c) == 1)
	{
	  for (i = 0; i < GRID_SIZE; i++)
	    {
	      if (c & mask)
		{
		  printf("%.2x ", i+1);
		  break;
		}
	      mask = mask << 1;
	    }
	}
      else
	{
	  printf(".. ");
	}
    }
  else if (type == 2)
    {
      if (bitCount(c) == 1)
	{
	  for (i = 0; i < GRID_SIZE; i++)
	    {
	      if (c & mask)
		{
		  printf("%c ", i+65);
		  break;
		}
	      mask = mask << 1;
	    }
	}
      else
	{
	  printf(". ");
	}
    }
  else
    {
      printf ("%s ", bin);
    }
}

Grid newGrid (void)
{
  Grid new = malloc(sizeof(cell) * GRID_SIZE * GRID_SIZE);
  return new;
}

void delGrid (Grid g)
{
  free (g);
}

void popGrid (char * input, Grid g)
{
  int x, y;
  for (y = 0; y < GRID_SIZE; y++)
    {
      for (x = 0; x < GRID_SIZE; x++)
	{
	  if ((gridIndex(input, x, y) >= '1') && (gridIndex(input, x, y) <= '9'))
	    {
	      setCell(gridIndex(input, x, y) - 48, &gridIndex(g, x, y));
	    }
	  else if ( (gridIndex(input, x, y) >= 'A') && (gridIndex(input, x, y) <= 'Z'))
	    {
	      setCell(gridIndex(input, x, y) - 64, &gridIndex(g, x, y));
	    }
	  else
	    {
	      gridIndex(g, x, y) = (0x1 << GRID_SIZE) - 1;
	    }
	}
    }
}

void prtGrid (Grid g, int type)
{
  int x, y;
  int num_solved = 0;
  for (y = 0; y < GRID_SIZE; y++)
    {
      for (x = 0; x < GRID_SIZE; x++)
	{
	  prtCell(gridIndex(g, x, y), type);
	  if (bitCount(gridIndex(g, x, y)) == 1) num_solved++;
	}
      printf ("\n");
    }
  printf("cells solved: %d\n", num_solved);
}

bool isGridSolved(Grid g)
{
  int x, y;
  for (y = 0; y < GRID_SIZE; y++)
    {
      for (x = 0; x < GRID_SIZE; x++)
	{
	  if (bitCount(gridIndex(g, x, y)) != 1)
	    {
	      return FALSE;
	    }
	}
    }
  return TRUE;
}

bool a1(Grid g)
{
  bool progress = TRUE;
  int x, y;
  while (progress)
    {
      progress = FALSE;
      for (y = 0; y < GRID_SIZE; y++)
	{
	  for (x = 0; x < GRID_SIZE; x++)
	    {
	      if (bitCount(gridIndex(g, x, y)) == 1)
		{
		  progress |= umkCell(g, x, y);
		}
	    }
	}
    }
  return isGridSolved (g);
}

  /* int iter = 0; */
  /* int x, y; */
  /* int sx, sy; */
  /* char input[10][GRID_SIZE * GRID_SIZE + 1] = */
  /*   {"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......", */
  /*    "..4..83.9...3.2.78.829..4.5.6..9..34...2.3...73..1..8.5.3..486.42.6.1...8.65..2..", */
  /*    "8.1...3.6.2.641.7.6.......2.3.8.4.9..1.....8..5.2.9.4.3.......1.9.387.6.4.7...9.8", */
  /*    "52...6.........7.13...........4..8..6......5...........418.........3..2...87.....", */
  /*    "6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....", */
  /*    "48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....", */
  /*    "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...", */
  /*    "......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.", */
  /*    "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....", */
  /*    "1234567894........5........6........7........8........9........2........3........"}; */
